package org.liaohailong.helloworld.study;

import org.liaohailong.helloworld.SortMethod;

import java.util.HashMap;
import java.util.Map;
import java.util.TreeSet;

/**
 * Author: liaohailong
 * Date: 2021/5/2
 * Time: 10:36
 * Description:
 **/
public class BinarySearch {

    /**
     * 创建一个乱序数组
     *
     * @param count 数组总长度
     * @return 乱序数组
     */
    public int[] create(int count) {
        final Map<Integer, Integer> map = new HashMap<>();
        map.put(0, -1);
        map.put(1, 1);
        map.put(2, 1);
        map.put(3, -1);
        map.put(4, 1);
        map.put(5, 1);
        map.put(6, -1);
        map.put(7, 1);
        map.put(8, 1);
        map.put(9, -1);

        TreeSet<Integer> treeSet = new TreeSet<>((o1, o2) -> {
            int o3 = o1 & o2;
            int o4 = o3 % 10;
            if (o4 < 0) o4 = -o4;
            return map.get(o4);
        });
        int start = -(count / 2);
        int end = count / 2;
        for (int i = start; i < end; i++) {
            treeSet.add(i);
        }

        int[] result = new int[count];
        int pos = 0;
        for (Integer next : treeSet) {
            result[pos] = next;
            pos++;
        }
        return result;
    }


    /**
     * @param arr 快速排序
     */
    public void quickSort(int[] arr) {
        SortMethod.quickSort(arr);
    }

    public void binarySearch(int[] arr, int target, int[] res) {
        int index = _binarySearch(arr, 0, arr.length - 1, target);
        res[0] = index;
    }


    public int _binarySearch(int[] arr, int left, int right, int target) {
        // 未找到的情况
        if (left > right) return -1;
        // 已经到了最后一次查找的机会
        if (left == right) return arr[left] == target ? left : -1;

        // 中间数查找，根据target与mid大小，判断左右分水岭
        int mid = left + (right - left) / 2;
        if (arr[mid] > target) {
            // find left
            return _binarySearch(arr, left, mid, target);
        } else if (arr[mid] < target) {
            // find right
            return _binarySearch(arr, mid + 1, right, target);
        } else {
            // find ok
            return mid;
        }
    }
}
